home *** CD-ROM | disk | FTP | other *** search
/ Windows Game Programming for Dummies (2nd Edition) / WinGamProgFD.iso / pc / DirectX SDK / DXSDK / samples / Multimedia / Direct3D / Cull / cull.cpp next >
Encoding:
C/C++ Source or Header  |  2001-10-08  |  45.2 KB  |  1,173 lines
  1. //-----------------------------------------------------------------------------
  2. // File: Cull.cpp
  3. //
  4. // Desc: Shows a technique for culling objects whose bounding boxes are 
  5. //       outside the view frustum.  This technique is described at:
  6. //       http://www.cs.unc.edu/~hoff/research/vfculler/viewcull.html
  7. //
  8. //       Note: This code uses the D3D Framework helper library.
  9. //
  10. // Copyright (c) 2000-2001 Microsoft Corporation. All rights reserved.
  11. //-----------------------------------------------------------------------------
  12. #define STRICT
  13. #include <math.h>
  14. #include <D3DX8.h>
  15. #include "D3DApp.h"
  16. #include "D3DFont.h"
  17. #include "D3DUtil.h"
  18. #include "DXUtil.h"
  19.  
  20.  
  21. //-----------------------------------------------------------------------------
  22. // Name: enum CULLSTATE
  23. // Desc: Represents the result of the culling calculation on an object.
  24. //-----------------------------------------------------------------------------
  25. enum CULLSTATE
  26. {
  27.     CS_UNKNOWN,      // cull state not yet computed
  28.     CS_INSIDE,       // object bounding box is at least partly inside the frustum
  29.     CS_OUTSIDE,      // object bounding box is outside the frustum
  30.     CS_INSIDE_SLOW,  // OBB is inside frustum, but it took extensive testing to determine this
  31.     CS_OUTSIDE_SLOW, // OBB is outside frustum, but it took extensive testing to determine this
  32. };
  33.  
  34.  
  35. //-----------------------------------------------------------------------------
  36. // Name: struct CULLINFO
  37. // Desc: Stores information that will be used when culling objects.  It needs
  38. //       to be recomputed whenever the view matrix or projection matrix changes.
  39. //-----------------------------------------------------------------------------
  40. struct CULLINFO
  41. {
  42.     D3DXVECTOR3 vecFrustum[8];    // corners of the view frustum
  43.     D3DXPLANE planeFrustum[6];    // planes of the view frustum
  44. };
  45.  
  46.  
  47. // Prototypes for the culling functions
  48. VOID UpdateCullInfo( CULLINFO* pCullInfo, D3DXMATRIX* pMatView, D3DXMATRIX* pMatProj );
  49. CULLSTATE CullObject( CULLINFO* pCullInfo, D3DXVECTOR3* pVecBounds, D3DXPLANE* pPlaneBounds );
  50. BOOL EdgeIntersectsFace( D3DXVECTOR3* pEdges, D3DXVECTOR3* pFaces, D3DXPLANE* pPlane );
  51.  
  52.  
  53. //-----------------------------------------------------------------------------
  54. // Name: struct PLANEVERTEX
  55. // Desc: Custom vertex type used for drawing the frustum planes
  56. //-----------------------------------------------------------------------------
  57. struct PLANEVERTEX
  58. {
  59.     D3DXVECTOR3 p;
  60.     DWORD       color;
  61. };
  62.  
  63. #define D3DFVF_PLANEVERTEX (D3DFVF_XYZ|D3DFVF_DIFFUSE)
  64.  
  65.  
  66. //-----------------------------------------------------------------------------
  67. // Name: class CCullableThing
  68. // Desc: A cullable object
  69. //-----------------------------------------------------------------------------
  70. class CCullableThing
  71. {
  72. public:
  73.     D3DXVECTOR3  m_pos;       // origin of object
  74.     FLOAT        m_fRotX;     // rotation of object around X axis
  75.     FLOAT        m_fRotY;     // rotation of object around Y axis
  76.     D3DXMATRIX   m_mat;       // object's local-to-world transformation
  77.     D3DXVECTOR3  m_vecBoundsLocal[8];   // bounding box coordinates (in local coord space)
  78.     D3DXVECTOR3  m_vecBoundsWorld[8];   // bounding box coordinates (in world coord space)
  79.     D3DXPLANE    m_planeBoundsWorld[6]; // bounding box planes (in world coord space)
  80.     CULLSTATE    m_cullstate; // whether object is in the view frustum
  81.  
  82. public:
  83.     VOID Init(VOID)
  84.     {
  85.         // Pick a random position and orientation
  86.         m_pos = D3DXVECTOR3( (FLOAT)(rand() % 50 - 25), // X is in (-25.0, 25.0)
  87.                              (FLOAT)(rand() % 50 - 25), // Y is in (-25.0, 25.0)
  88.                              (FLOAT)(rand() % 25) );    // Z is in (  0.0, 25.0)
  89.         m_fRotX = D3DXToRadian(rand() % 360);
  90.         m_fRotY = D3DXToRadian(rand() % 360);
  91.         UpdateMatrix();
  92.         m_cullstate = CS_UNKNOWN;
  93.     }
  94.     VOID UpdateMatrix(VOID)
  95.     {
  96.         // Recompute m_mat, m_vecBoundsWorld, and m_planeBoundsWorld 
  97.         // when the thing's position, orientation, or bounding box has changed
  98.         D3DXMATRIX matRotX, matRotY, matTrans;
  99.         D3DXMatrixRotationX( &matRotX, m_fRotX );
  100.         D3DXMatrixRotationY( &matRotY, m_fRotY );
  101.         D3DXMatrixTranslation( &matTrans, m_pos.x, m_pos.y, m_pos.z );
  102.         m_mat = matRotX * matRotY * matTrans;
  103.  
  104.         // Transform bounding box coords from local space to world space
  105.         for( int i = 0; i < 8; i++ )
  106.             D3DXVec3TransformCoord( &m_vecBoundsWorld[i], &m_vecBoundsLocal[i], &m_mat );
  107.  
  108.         // Determine planes of the bounding box
  109.         D3DXPlaneFromPoints( &m_planeBoundsWorld[0], &m_vecBoundsWorld[0], 
  110.             &m_vecBoundsWorld[1], &m_vecBoundsWorld[2] ); // Near
  111.         D3DXPlaneFromPoints( &m_planeBoundsWorld[1], &m_vecBoundsWorld[6], 
  112.             &m_vecBoundsWorld[7], &m_vecBoundsWorld[5] ); // Far
  113.         D3DXPlaneFromPoints( &m_planeBoundsWorld[2], &m_vecBoundsWorld[2], 
  114.             &m_vecBoundsWorld[6], &m_vecBoundsWorld[4] ); // Left
  115.         D3DXPlaneFromPoints( &m_planeBoundsWorld[3], &m_vecBoundsWorld[7], 
  116.             &m_vecBoundsWorld[3], &m_vecBoundsWorld[5] ); // Right
  117.         D3DXPlaneFromPoints( &m_planeBoundsWorld[4], &m_vecBoundsWorld[2], 
  118.             &m_vecBoundsWorld[3], &m_vecBoundsWorld[6] ); // Top
  119.         D3DXPlaneFromPoints( &m_planeBoundsWorld[5], &m_vecBoundsWorld[1], 
  120.             &m_vecBoundsWorld[0], &m_vecBoundsWorld[4] ); // Bottom
  121.     }
  122. };
  123.  
  124.  
  125. //-----------------------------------------------------------------------------
  126. // Name: struct Camera
  127. // Desc: 
  128. //-----------------------------------------------------------------------------
  129. struct Camera
  130. {
  131.     D3DXVECTOR3        m_vPosition;
  132.     D3DXVECTOR3        m_vVelocity;
  133.     FLOAT              m_fYaw;
  134.     FLOAT              m_fYawVelocity;
  135.     FLOAT              m_fPitch;
  136.     FLOAT              m_fPitchVelocity;
  137.     D3DXMATRIX         m_matView;
  138.     D3DXMATRIX         m_matOrientation;
  139. };
  140.  
  141.  
  142. //-----------------------------------------------------------------------------
  143. // Name: class CMyD3DApplication
  144. // Desc: Application class. The base class (CD3DApplication) provides the 
  145. //       generic functionality needed in all Direct3D samples. CMyD3DApplication 
  146. //       adds functionality specific to this sample program.
  147. //-----------------------------------------------------------------------------
  148. class CMyD3DApplication : public CD3DApplication
  149. {
  150.     CD3DFont*      m_pFont;       // Font for drawing text
  151.     CD3DFont*      m_pFontSmall;
  152.  
  153.     LPD3DXMESH     m_pMeshTeapot; // Mesh of thing to be cull-tested
  154.     LPD3DXMESH     m_pMeshBox;    // Mesh to visualize bounding box
  155.     D3DXMATRIX     m_matBox;      // Matrix that places bounding box correctly on teapot
  156.  
  157.     LPDIRECT3DVERTEXBUFFER8 m_pPlaneVB[6]; // VBs to visualize the view frustum
  158.  
  159.     // The things to render and cull
  160.     CCullableThing m_CullableThingArray[50];
  161.     DWORD          m_dwNumCullableThings;
  162.  
  163.     // Variables for determining the view
  164.     BYTE           m_bKey[256];
  165.     BOOL           m_bLeftActive; // left vs right view currently active
  166.     Camera         m_CameraLeft;
  167.     Camera         m_CameraRight;
  168.     D3DXMATRIX     m_matProjLeft;
  169.     D3DXMATRIX     m_matProjRight;
  170.  
  171.     D3DMATERIAL8   m_mtrlOutside;
  172.     D3DMATERIAL8   m_mtrlInside;
  173.     D3DMATERIAL8   m_mtrlOutsideSlow;
  174.     D3DMATERIAL8   m_mtrlInsideSlow;
  175.     D3DMATERIAL8   m_mtrlWhite;
  176.  
  177.     CULLINFO       m_cullinfo;
  178.     BOOL           m_bShowHelp;
  179.  
  180. protected:
  181.     HRESULT OneTimeSceneInit();
  182.     HRESULT InitDeviceObjects();
  183.     HRESULT RestoreDeviceObjects();
  184.     HRESULT InvalidateDeviceObjects();
  185.     HRESULT DeleteDeviceObjects();
  186.     HRESULT Render();
  187.     HRESULT RenderScene( BOOL bRenderPlanes );
  188.     HRESULT FrameMove();
  189.     HRESULT FinalCleanup();
  190.     VOID    UpdateCamera(Camera* pCamera);
  191.     HRESULT UpdatePlaneVBs(VOID);
  192.     VOID    CullObjects(VOID);
  193.  
  194. public:
  195.     CMyD3DApplication();
  196.     LRESULT MsgProc( HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam );
  197. };
  198.  
  199.  
  200.  
  201.  
  202.  
  203. //-----------------------------------------------------------------------------
  204. // Name: WinMain()
  205. // Desc: Entry point to the program. Initializes everything, and goes into a
  206. //       message-processing loop. Idle time is used to render the scene.
  207. //-----------------------------------------------------------------------------
  208. INT WINAPI WinMain( HINSTANCE hInst, HINSTANCE, LPSTR, INT )
  209. {
  210.     CMyD3DApplication d3dApp;
  211.  
  212.     if( FAILED( d3dApp.Create( hInst ) ) )
  213.         return 0;
  214.  
  215.     return d3dApp.Run();
  216. }
  217.  
  218.  
  219.  
  220.  
  221. //-----------------------------------------------------------------------------
  222. // Name: CMyD3DApplication()
  223. // Desc: Application constructor. Sets attributes for the app.
  224. //-----------------------------------------------------------------------------
  225. CMyD3DApplication::CMyD3DApplication()
  226. {
  227.     m_strWindowTitle    = _T("Cull: Culling nonvisible objects");
  228.     m_bUseDepthBuffer   = TRUE;
  229.     m_dwCreationWidth   = 600;
  230.     m_dwCreationHeight  = 300;
  231.     m_bShowCursorWhenFullscreen = TRUE;
  232.  
  233.     m_pFont             = new CD3DFont( _T("Arial"), 12, D3DFONT_BOLD );
  234.     m_pFontSmall        = new CD3DFont( _T("Arial"),  9, D3DFONT_BOLD );
  235.     m_pMeshTeapot       = NULL;
  236.     m_pMeshBox          = NULL;
  237.     m_dwNumCullableThings = 0;
  238.  
  239.     ZeroMemory( m_pPlaneVB, sizeof(m_pPlaneVB) );
  240.     ZeroMemory( m_bKey, 256 );
  241.     ZeroMemory( &m_CameraLeft, sizeof(m_CameraLeft) );
  242.     ZeroMemory( &m_CameraRight, sizeof(m_CameraRight) );
  243.  
  244.     m_bLeftActive = TRUE;
  245.     m_bShowHelp = FALSE;
  246. }
  247.  
  248.  
  249.  
  250.  
  251. //-----------------------------------------------------------------------------
  252. // Name: OneTimeSceneInit()
  253. // Desc: Called during initial app startup, this function performs all the
  254. //       permanent initialization.
  255. //-----------------------------------------------------------------------------
  256. HRESULT CMyD3DApplication::OneTimeSceneInit()
  257. {
  258.     // Initialize cullable things
  259.     for( int i = 0; i < 50; i++ )
  260.     {
  261.         m_CullableThingArray[m_dwNumCullableThings].Init();
  262.         m_dwNumCullableThings++;
  263.     }
  264.  
  265.     UpdateCamera( &m_CameraLeft );
  266.     UpdateCamera( &m_CameraRight );
  267.  
  268.     return S_OK;
  269. }
  270.  
  271.  
  272.  
  273.  
  274. //-----------------------------------------------------------------------------
  275. // Name: FrameMove()
  276. // Desc: Called once per frame, the call is the entry point for animating
  277. //       the scene.
  278. //-----------------------------------------------------------------------------
  279. HRESULT CMyD3DApplication::FrameMove()
  280. {
  281.     BOOL bNeedToCull = FALSE;
  282.  
  283.     // Handle object rotations
  284.     if( m_bKey['Y'] || m_bKey['U'] || m_bKey['H'] || m_bKey['J'])
  285.     {
  286.         CCullableThing* pCullableThing;
  287.         for( DWORD iThing = 0; iThing < m_dwNumCullableThings; iThing++ )
  288.         {
  289.             pCullableThing = &m_CullableThingArray[iThing];
  290.             if( m_bKey['Y'] )
  291.                 pCullableThing->m_fRotY += m_fElapsedTime;
  292.             else if( m_bKey['U'] )
  293.                 pCullableThing->m_fRotY -= m_fElapsedTime;
  294.             if( m_bKey['H'] )
  295.                 pCullableThing->m_fRotX += m_fElapsedTime;
  296.             else if( m_bKey['J'] )
  297.                 pCullableThing->m_fRotX -= m_fElapsedTime;
  298.             pCullableThing->UpdateMatrix();
  299.         }
  300.         bNeedToCull = TRUE;
  301.     }
  302.  
  303.     // Handle camera motion
  304.     UpdateCamera(m_bLeftActive ? &m_CameraLeft : &m_CameraRight);
  305.     if( !m_bLeftActive )
  306.     {
  307.         UpdateCullInfo( &m_cullinfo, &m_CameraRight.m_matView, &m_matProjRight );
  308.         bNeedToCull = TRUE;
  309.         UpdatePlaneVBs();
  310.     }
  311.  
  312.     // Re-determine cull state of all objects if necessary
  313.     if( bNeedToCull )
  314.         CullObjects();
  315.  
  316.     return S_OK;
  317. }
  318.  
  319.  
  320.  
  321.  
  322. //-----------------------------------------------------------------------------
  323. // Name: Render()
  324. // Desc: Called once per frame, the call is the entry point for 3d
  325. //       rendering. This function sets up render states, clears the
  326. //       viewport, and renders the scene.
  327. //-----------------------------------------------------------------------------
  328. HRESULT CMyD3DApplication::Render()
  329. {
  330.     // The "hot" clear color is used to indicate the viewport
  331.     // whose camera is currently being controlled by the keyboard
  332.     const DWORD dwHotClearColor = 0xff0000ff;
  333.     const DWORD dwColdClearColor = 0xff000080;
  334.  
  335.     //
  336.     // Draw left viewport
  337.     //
  338.     D3DVIEWPORT8 vp;
  339.     vp.X = 0;
  340.     vp.Y = 0;
  341.     vp.Width = m_d3dsdBackBuffer.Width / 2;
  342.     vp.Height = m_d3dsdBackBuffer.Height;
  343.     vp.MinZ = 0.0f;
  344.     vp.MaxZ = 1.0f;
  345.     m_pd3dDevice->SetViewport( &vp );
  346.  
  347.     m_pd3dDevice->Clear( 0L, NULL, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 
  348.         m_bLeftActive ? dwHotClearColor : dwColdClearColor, 1.0f, 0L );
  349.  
  350.     m_pd3dDevice->SetTransform( D3DTS_VIEW, &m_CameraLeft.m_matView );
  351.     m_pd3dDevice->SetTransform( D3DTS_PROJECTION, &m_matProjLeft );
  352.  
  353.     // Draw contents of left viewport
  354.     RenderScene( TRUE ); // TRUE means render frustum planes
  355.  
  356.     //
  357.     // Draw right viewport
  358.     //
  359.     vp.X = m_d3dsdBackBuffer.Width / 2;
  360.     vp.Width = m_d3dsdBackBuffer.Width / 2;
  361.     m_pd3dDevice->SetViewport( &vp );
  362.  
  363.     m_pd3dDevice->Clear( 0L, NULL, D3DCLEAR_TARGET|D3DCLEAR_ZBUFFER,
  364.         m_bLeftActive ? dwColdClearColor : dwHotClearColor, 1.0f, 0L );
  365.  
  366.     m_pd3dDevice->SetTransform( D3DTS_VIEW, &m_CameraRight.m_matView );
  367.     m_pd3dDevice->SetTransform( D3DTS_PROJECTION, &m_matProjRight );
  368.  
  369.     // Draw contents of right viewport
  370.     RenderScene( FALSE ); // FALSE means don't render frustum planes
  371.  
  372.     return S_OK;
  373. }
  374.  
  375.  
  376.  
  377.  
  378. //-----------------------------------------------------------------------------
  379. // Name: RenderScene()
  380. // Desc: 
  381. //-----------------------------------------------------------------------------
  382. HRESULT CMyD3DApplication::RenderScene( BOOL bRenderPlanes )
  383. {
  384.     // Begin the scene
  385.     if( SUCCEEDED( m_pd3dDevice->BeginScene() ) )
  386.     {
  387.         // Render each object
  388.         CCullableThing* pCullableThing;
  389.         for( DWORD iThing = 0; iThing < m_dwNumCullableThings; iThing++ )
  390.         {
  391.             pCullableThing = &m_CullableThingArray[iThing];
  392.  
  393.             // Normally, if the cullstate is CS_OUTSIDE or CS_OUTSIDE_SLOW,
  394.             // there is no need to ask D3D to render the object since
  395.             // it's outside the view frustum.  Since this app is meant to
  396.             // visualize the culling process, all objects are passed to D3D,
  397.             // and different colors are used to show their cullstates.
  398.  
  399.             switch( pCullableThing->m_cullstate )
  400.             {
  401.             case CS_UNKNOWN:
  402.                 m_pd3dDevice->SetMaterial( &m_mtrlWhite );
  403.                 break;
  404.             case CS_OUTSIDE:
  405.                 m_pd3dDevice->SetMaterial( &m_mtrlOutside );
  406.                 break;
  407.             case CS_INSIDE:
  408.                 m_pd3dDevice->SetMaterial( &m_mtrlInside );
  409.                 break;
  410.             case CS_OUTSIDE_SLOW:
  411.                 m_pd3dDevice->SetMaterial( &m_mtrlOutsideSlow );
  412.                 break;
  413.             case CS_INSIDE_SLOW:
  414.                 m_pd3dDevice->SetMaterial( &m_mtrlInsideSlow );
  415.                 break;
  416.             }
  417.             m_pd3dDevice->SetTransform( D3DTS_WORLD, &pCullableThing->m_mat );
  418.             m_pMeshTeapot->DrawSubset( 0 );
  419.             D3DXMATRIX mat = m_matBox * pCullableThing->m_mat;
  420.             m_pd3dDevice->SetTransform( D3DTS_WORLD, &mat );
  421.             m_pd3dDevice->SetRenderState( D3DRS_ALPHABLENDENABLE, TRUE );
  422.             m_pMeshBox->DrawSubset( 0 );
  423.             m_pd3dDevice->SetRenderState( D3DRS_ALPHABLENDENABLE, FALSE );
  424.         }
  425.  
  426.         if( bRenderPlanes )
  427.         {
  428.             // Render frustum planes
  429.             m_pd3dDevice->SetMaterial( &m_mtrlWhite );
  430.             D3DXMATRIX mat;
  431.             D3DXMatrixIdentity( &mat );
  432.             m_pd3dDevice->SetTransform( D3DTS_WORLD, &mat );
  433.             m_pd3dDevice->SetRenderState( D3DRS_CULLMODE, D3DCULL_NONE );
  434.             m_pd3dDevice->SetVertexShader( D3DFVF_PLANEVERTEX );
  435.             m_pd3dDevice->SetRenderState( D3DRS_ALPHABLENDENABLE, TRUE );
  436.             for( int iPlane = 0; iPlane < 6; iPlane++ )
  437.             {
  438.                 m_pd3dDevice->SetStreamSource( 0, m_pPlaneVB[iPlane], sizeof(PLANEVERTEX) );
  439.                 m_pd3dDevice->DrawPrimitive( D3DPT_TRIANGLESTRIP, 0, 2 );
  440.             }
  441.             m_pd3dDevice->SetRenderState( D3DRS_ALPHABLENDENABLE, FALSE );
  442.             m_pd3dDevice->SetRenderState( D3DRS_CULLMODE, D3DCULL_CCW );
  443.         }
  444.  
  445.         // Output statistics
  446.         m_pFont->DrawText( 2,  0, D3DCOLOR_ARGB(255,255,255,0), m_strFrameStats );
  447.         m_pFont->DrawText( 2, 20, D3DCOLOR_ARGB(255,255,255,0), m_strDeviceStats );
  448.         
  449.         // Show help
  450.         if( m_bShowHelp )
  451.         {
  452.             m_pFontSmall->DrawText(  2, 40, D3DCOLOR_ARGB(255,200,100,100),
  453.                                     _T("Press F1 to hide help\n")
  454.                                     _T("The right viewport is the frustum being culled against.\n")
  455.                                     _T("The left viewport has its own camera that lets you view\n")
  456.                                     _T("the scene and frustum from different angles.\n")
  457.                                     _T("Click the viewport whose camera you want to control.\n")
  458.                                     _T("Keyboard controls:") );
  459.             m_pFontSmall->DrawText( 20, 140, D3DCOLOR_ARGB(255,200,100,100),
  460.                                     _T("Move\n")
  461.                                     _T("Turn\n")
  462.                                     _T("Spin objects\n")
  463.                                     _T("Snap left view to viewport\n")
  464.                                     _T("Snap right view to origin\n") );
  465.             m_pFontSmall->DrawText( 210, 140, D3DCOLOR_ARGB(255,200,100,100),
  466.                                     _T("W, S, Arrow keys\n")
  467.                                     _T("Q, E, A, Z\n")
  468.                                     _T("Y, U, H, J\n")
  469.                                     _T("N\n")
  470.                                     _T("M") );
  471.         }
  472.         else
  473.         {
  474.             m_pFontSmall->DrawText(  2, 40, D3DCOLOR_ARGB(255,200,100,100), 
  475.                                _T("Press F1 for help") );
  476.         }
  477.  
  478.         // End the scene.
  479.         m_pd3dDevice->EndScene();
  480.     }
  481.  
  482.     return S_OK;
  483. }
  484.  
  485.  
  486.  
  487.  
  488. //-----------------------------------------------------------------------------
  489. // Name: UpdateCamera()
  490. // Desc: 
  491. //-----------------------------------------------------------------------------
  492. VOID CMyD3DApplication::UpdateCamera(Camera* pCamera)
  493. {
  494.     FLOAT fElapsedTime;
  495.  
  496.     if( m_fElapsedTime > 0.0f )
  497.         fElapsedTime = m_fElapsedTime;
  498.     else
  499.         fElapsedTime = 0.05f;
  500.  
  501.     FLOAT fSpeed        = 5.0f*fElapsedTime;
  502.     FLOAT fAngularSpeed = 2.0f*fElapsedTime;
  503.  
  504.     // De-accelerate the camera movement (for smooth motion)
  505.     pCamera->m_vVelocity      *= 0.75f;
  506.     pCamera->m_fYawVelocity   *= 0.75f;
  507.     pCamera->m_fPitchVelocity *= 0.75f;
  508.  
  509.     // Process keyboard input
  510.     if( m_bKey[VK_RIGHT] )    pCamera->m_vVelocity.x    += fSpeed; // Slide Right
  511.     if( m_bKey[VK_LEFT] )     pCamera->m_vVelocity.x    -= fSpeed; // Slide Left
  512.     if( m_bKey[VK_UP] )       pCamera->m_vVelocity.y    += fSpeed; // Slide Up
  513.     if( m_bKey[VK_DOWN] )     pCamera->m_vVelocity.y    -= fSpeed; // Slide Down
  514.     if( m_bKey['W'] )         pCamera->m_vVelocity.z    += fSpeed; // Move Forward
  515.     if( m_bKey['S'] )         pCamera->m_vVelocity.z    -= fSpeed; // Move Backward
  516.     if( m_bKey['E'] )         pCamera->m_fYawVelocity   += fSpeed; // Turn Right
  517.     if( m_bKey['Q'] )         pCamera->m_fYawVelocity   -= fSpeed; // Turn Left
  518.     if( m_bKey['Z'] )         pCamera->m_fPitchVelocity += fSpeed; // Turn Down
  519.     if( m_bKey['A'] )         pCamera->m_fPitchVelocity -= fSpeed; // Turn Up
  520.  
  521.     // Update the position vector
  522.     D3DXVECTOR3 vT = pCamera->m_vVelocity * fSpeed;
  523.     D3DXVec3TransformNormal( &vT, &vT, &pCamera->m_matOrientation );
  524.     pCamera->m_vPosition += vT;
  525.  
  526.     // Update the yaw-pitch-rotation vector
  527.     pCamera->m_fYaw   += fAngularSpeed * pCamera->m_fYawVelocity;
  528.     pCamera->m_fPitch += fAngularSpeed * pCamera->m_fPitchVelocity;
  529.     if( pCamera->m_fPitch < -D3DX_PI/2 ) 
  530.         pCamera->m_fPitch = -D3DX_PI/2;
  531.     if( pCamera->m_fPitch > D3DX_PI/2 ) 
  532.         pCamera->m_fPitch = D3DX_PI/2;
  533.  
  534.     // Set the view matrix
  535.     D3DXQUATERNION qR;
  536.     D3DXQuaternionRotationYawPitchRoll( &qR, pCamera->m_fYaw, pCamera->m_fPitch, 0.0f );
  537.     D3DXMatrixAffineTransformation( &pCamera->m_matOrientation, 1.25f, NULL, &qR, &pCamera->m_vPosition );
  538.     D3DXMatrixInverse( &pCamera->m_matView, NULL, &pCamera->m_matOrientation );
  539. }
  540.  
  541.  
  542.  
  543.  
  544. //-----------------------------------------------------------------------------
  545. // Name: UpdatePlaneVBs()
  546. // Desc: Update the vertex buffers to match the view frustum.  Slightly 
  547. //       different colors are used for each plane to make them easier to
  548. //       distinguish from each other.
  549. //-----------------------------------------------------------------------------
  550. HRESULT CMyD3DApplication::UpdatePlaneVBs()
  551. {
  552.     HRESULT hr;
  553.     for( int iPlane = 0; iPlane < 6; iPlane++ )
  554.     {
  555.         PLANEVERTEX* v;
  556.         if( FAILED(hr = m_pPlaneVB[iPlane]->Lock( 0, 0, (BYTE**)&v, 0 ) ) )
  557.             return hr;
  558.         switch( iPlane )
  559.         {
  560.         case 0: // near
  561.             v[0].p = m_cullinfo.vecFrustum[0];
  562.             v[1].p = m_cullinfo.vecFrustum[1];
  563.             v[2].p = m_cullinfo.vecFrustum[2];
  564.             v[3].p = m_cullinfo.vecFrustum[3];
  565.             v[0].color = v[1].color = v[2].color = v[3].color = 0x80505050;
  566.             break;
  567.         case 1: // far
  568.             v[0].p = m_cullinfo.vecFrustum[4];
  569.             v[1].p = m_cullinfo.vecFrustum[6];
  570.             v[2].p = m_cullinfo.vecFrustum[5];
  571.             v[3].p = m_cullinfo.vecFrustum[7];
  572.             v[0].color = v[1].color = v[2].color = v[3].color = 0x80404040;
  573.             break;
  574.         case 2: // left
  575.             v[0].p = m_cullinfo.vecFrustum[0];
  576.             v[1].p = m_cullinfo.vecFrustum[2];
  577.             v[2].p = m_cullinfo.vecFrustum[4];
  578.             v[3].p = m_cullinfo.vecFrustum[6];
  579.             v[0].color = v[1].color = v[2].color = v[3].color = 0x80404040;
  580.             break;
  581.         case 3:
  582.             v[0].p = m_cullinfo.vecFrustum[1];
  583.             v[1].p = m_cullinfo.vecFrustum[3];
  584.             v[2].p = m_cullinfo.vecFrustum[5];
  585.             v[3].p = m_cullinfo.vecFrustum[7];
  586.             v[0].color = v[1].color = v[2].color = v[3].color = 0x80606060;
  587.             break;
  588.         case 4:
  589.             v[0].p = m_cullinfo.vecFrustum[2];
  590.             v[1].p = m_cullinfo.vecFrustum[3];
  591.             v[2].p = m_cullinfo.vecFrustum[6];
  592.             v[3].p = m_cullinfo.vecFrustum[7];
  593.             v[0].color = v[1].color = v[2].color = v[3].color = 0x80505050;
  594.             break;
  595.         case 5:
  596.             v[0].p = m_cullinfo.vecFrustum[0];
  597.             v[1].p = m_cullinfo.vecFrustum[1];
  598.             v[2].p = m_cullinfo.vecFrustum[4];
  599.             v[3].p = m_cullinfo.vecFrustum[5];
  600.             v[0].color = v[1].color = v[2].color = v[3].color = 0x80505050;
  601.             break;
  602.         }
  603.         m_pPlaneVB[iPlane]->Unlock();
  604.     }
  605.  
  606.     return S_OK;
  607. }
  608.  
  609.  
  610.  
  611. //-----------------------------------------------------------------------------
  612. // Name: InitDeviceObjects()
  613. // Desc: Initialize scene objects.
  614. //-----------------------------------------------------------------------------
  615. HRESULT CMyD3DApplication::InitDeviceObjects()
  616. {
  617.     HRESULT hr;
  618.  
  619.     // Initialize the font's internal textures
  620.     if( FAILED( hr = m_pFont->InitDeviceObjects( m_pd3dDevice ) ) )
  621.         return hr;
  622.     if( FAILED( hr = m_pFontSmall->InitDeviceObjects( m_pd3dDevice ) ) )
  623.         return hr;
  624.  
  625.     // Create a teapot mesh
  626.     if( FAILED( D3DXCreateTeapot( m_pd3dDevice, &m_pMeshTeapot, NULL ) ) )
  627.         return hr;
  628.     D3DXComputeNormals( m_pMeshTeapot, NULL );
  629.  
  630.     // Determine bounding box of the teapot
  631.     D3DXVECTOR3 vecMin;
  632.     D3DXVECTOR3 vecMax;
  633.     BYTE* pVertices;
  634.     if( FAILED( hr = m_pMeshTeapot->LockVertexBuffer(D3DLOCK_READONLY, &pVertices) ) )
  635.         return hr;
  636.     hr = D3DXComputeBoundingBox( pVertices, m_pMeshTeapot->GetNumVertices(), 
  637.         m_pMeshTeapot->GetFVF(), &vecMin, &vecMax );
  638.     m_pMeshTeapot->UnlockVertexBuffer();
  639.  
  640.     // Note that the m_vecBoundsLocal are identical for every CullableThing
  641.     // because the cullable things are all the same teapot object.  In a real 
  642.     // app, of course, they would all be potentially different.
  643.     CCullableThing* pCullableThing;
  644.     for( DWORD iThing = 0; iThing < m_dwNumCullableThings; iThing++ )
  645.     {
  646.         pCullableThing = &m_CullableThingArray[iThing];
  647.         pCullableThing->m_vecBoundsLocal[0] = D3DXVECTOR3( vecMin.x, vecMin.y, vecMin.z ); // xyz
  648.         pCullableThing->m_vecBoundsLocal[1] = D3DXVECTOR3( vecMax.x, vecMin.y, vecMin.z ); // Xyz
  649.         pCullableThing->m_vecBoundsLocal[2] = D3DXVECTOR3( vecMin.x, vecMax.y, vecMin.z ); // xYz
  650.         pCullableThing->m_vecBoundsLocal[3] = D3DXVECTOR3( vecMax.x, vecMax.y, vecMin.z ); // XYz
  651.         pCullableThing->m_vecBoundsLocal[4] = D3DXVECTOR3( vecMin.x, vecMin.y, vecMax.z ); // xyZ
  652.         pCullableThing->m_vecBoundsLocal[5] = D3DXVECTOR3( vecMax.x, vecMin.y, vecMax.z ); // XyZ
  653.         pCullableThing->m_vecBoundsLocal[6] = D3DXVECTOR3( vecMin.x, vecMax.y, vecMax.z ); // xYZ
  654.         pCullableThing->m_vecBoundsLocal[7] = D3DXVECTOR3( vecMax.x, vecMax.y, vecMax.z ); // XYZ
  655.         pCullableThing->UpdateMatrix();
  656.     }
  657.  
  658.     // Set up m_matBox to be able to render the bounding box properly
  659.     D3DXMATRIX matTrans;
  660.     D3DXMATRIX matScale;
  661.     D3DXMatrixTranslation( &matTrans, (vecMin.x + vecMax.x) / 2, 
  662.         (vecMin.y + vecMax.y) / 2, (vecMin.z + vecMax.z) / 2 );
  663.     D3DXMatrixScaling( &matScale, vecMax.x - vecMin.x, vecMax.y - vecMin.y, vecMax.z - vecMin.z );
  664.     m_matBox = matScale * matTrans;
  665.  
  666.     if( FAILED( hr = D3DXCreateBox( m_pd3dDevice, 1.0f, 1.0f, 1.0f, &m_pMeshBox, NULL ) ) )
  667.         return hr;
  668.     D3DXComputeNormals( m_pMeshBox, NULL );
  669.  
  670.     // Create VBs for frustum planes
  671.     for( int iPlane = 0; iPlane < 6; iPlane++ )
  672.     {
  673.         if( FAILED( hr = m_pd3dDevice->CreateVertexBuffer( 4*sizeof(PLANEVERTEX),
  674.             D3DUSAGE_WRITEONLY, D3DFVF_PLANEVERTEX, D3DPOOL_MANAGED, &m_pPlaneVB[iPlane] ) ) )
  675.         {
  676.             return hr;
  677.         }
  678.     }
  679.  
  680.     return S_OK;
  681. }
  682.  
  683.  
  684.  
  685.  
  686. //-----------------------------------------------------------------------------
  687. // Name: RestoreDeviceObjects()
  688. // Desc: Initialize scene objects.
  689. //-----------------------------------------------------------------------------
  690. HRESULT CMyD3DApplication::RestoreDeviceObjects()
  691. {
  692.     m_pFont->RestoreDeviceObjects();
  693.     m_pFontSmall->RestoreDeviceObjects();
  694.  
  695.     // Set miscellaneous render states
  696.     m_pd3dDevice->SetRenderState( D3DRS_DITHERENABLE,   TRUE );
  697.     m_pd3dDevice->SetRenderState( D3DRS_ZENABLE,        TRUE );
  698.  
  699.     m_pd3dDevice->SetRenderState( D3DRS_SRCBLEND,       D3DBLEND_SRCALPHA );
  700.     m_pd3dDevice->SetRenderState( D3DRS_DESTBLEND,      D3DBLEND_INVSRCALPHA );
  701.  
  702.     // Set up the matrices
  703.     FLOAT fAspect = m_d3dsdBackBuffer.Width / (FLOAT)m_d3dsdBackBuffer.Height;
  704.     D3DXMatrixPerspectiveFovLH( &m_matProjRight, D3DX_PI/4, fAspect, 0.2f, 10.0f );
  705.     D3DXMatrixPerspectiveFovLH( &m_matProjLeft, D3DX_PI/4, fAspect, 0.2f, 200.0f );
  706.  
  707.     // Set up a light
  708.     if( ( m_d3dCaps.VertexProcessingCaps & D3DVTXPCAPS_DIRECTIONALLIGHTS ) ||
  709.        !( m_dwCreateFlags & D3DCREATE_HARDWARE_VERTEXPROCESSING ) )
  710.     {
  711.         D3DLIGHT8 light;
  712.         D3DUtil_InitLight( light, D3DLIGHT_DIRECTIONAL, 0.2f, -0.4f, 0.2f );
  713.         m_pd3dDevice->SetLight( 0, &light );
  714.         m_pd3dDevice->LightEnable( 0, TRUE );
  715.     }
  716.     m_pd3dDevice->SetRenderState( D3DRS_AMBIENT, 0xff555555 );
  717.  
  718.     // Set up materials
  719.     D3DUtil_InitMaterial(m_mtrlInside,      0.2f, 0.6f, 0.2f, 0.5f); // dark green
  720.     D3DUtil_InitMaterial(m_mtrlOutside,     0.6f, 0.2f, 0.2f, 0.5f); // dark red
  721.     D3DUtil_InitMaterial(m_mtrlInsideSlow,  0.7f, 1.0f, 0.7f, 0.5f); // pastel green
  722.     D3DUtil_InitMaterial(m_mtrlOutsideSlow, 1.0f, 0.7f, 0.7f, 0.5f); // pastel red
  723.     D3DUtil_InitMaterial(m_mtrlWhite,       1.0f, 1.0f, 1.0f, 0.5f); // white
  724.  
  725.     UpdateCullInfo( &m_cullinfo, &m_CameraRight.m_matView, &m_matProjRight );
  726.     CullObjects();
  727.     UpdatePlaneVBs();
  728.  
  729.     return S_OK;
  730. }
  731.  
  732.  
  733.  
  734.  
  735. //-----------------------------------------------------------------------------
  736. // Name: InvalidateDeviceObjects()
  737. // Desc:
  738. //-----------------------------------------------------------------------------
  739. HRESULT CMyD3DApplication::InvalidateDeviceObjects()
  740. {
  741.     m_pFont->InvalidateDeviceObjects();
  742.     m_pFontSmall->InvalidateDeviceObjects();
  743.  
  744.     return S_OK;
  745. }
  746.  
  747.  
  748.  
  749.  
  750. //-----------------------------------------------------------------------------
  751. // Name: DeleteDeviceObjects()
  752. // Desc: Called when the app is exiting, or the device is being changed,
  753. //       this function deletes any device dependent objects.
  754. //-----------------------------------------------------------------------------
  755. HRESULT CMyD3DApplication::DeleteDeviceObjects()
  756. {
  757.     m_pFont->DeleteDeviceObjects();
  758.     m_pFontSmall->DeleteDeviceObjects();
  759.     SAFE_RELEASE( m_pMeshTeapot );
  760.     SAFE_RELEASE( m_pMeshBox );
  761.  
  762.     for( int iPlane = 0; iPlane < 6; iPlane++ )
  763.         SAFE_RELEASE( m_pPlaneVB[iPlane] );
  764.  
  765.     return S_OK;
  766. }
  767.  
  768.  
  769.  
  770.  
  771. //-----------------------------------------------------------------------------
  772. // Name: FinalCleanup()
  773. // Desc: Called before the app exits, this function gives the app the chance
  774. //       to cleanup after itself.
  775. //-----------------------------------------------------------------------------
  776. HRESULT CMyD3DApplication::FinalCleanup()
  777. {
  778.     SAFE_DELETE( m_pFont );
  779.     SAFE_DELETE( m_pFontSmall );
  780.  
  781.     return S_OK;
  782. }
  783.  
  784.  
  785.  
  786.  
  787. //-----------------------------------------------------------------------------
  788. // Name: MsgProc()
  789. // Desc: Message proc function to handle key and menu input
  790. //-----------------------------------------------------------------------------
  791. LRESULT CMyD3DApplication::MsgProc( HWND hWnd, UINT uMsg, WPARAM wParam,
  792.                                     LPARAM lParam )
  793. {
  794.     // Record key presses
  795.     if( WM_KEYDOWN == uMsg )
  796.     {
  797.         m_bKey[wParam] = 1;
  798.     }
  799.     // Perform commands when keys are released
  800.     if( WM_KEYUP == uMsg )
  801.     {
  802.         m_bKey[wParam] = 0;
  803.         switch( wParam )
  804.         {
  805.         case 'N': // Set left camera to match right camera
  806.             m_CameraLeft = m_CameraRight;
  807.             break;
  808.         case 'M': // Reset right camera to original orientation
  809.             ZeroMemory( &m_CameraRight, sizeof(m_CameraRight) );
  810.             UpdateCamera( &m_CameraRight );
  811.             UpdateCullInfo( &m_cullinfo, &m_CameraRight.m_matView, &m_matProjRight );
  812.             CullObjects();
  813.             UpdatePlaneVBs();
  814.             break;
  815.         case VK_F1:
  816.             m_bShowHelp = !m_bShowHelp;
  817.             break;
  818.         }
  819.     }
  820.     if( WM_LBUTTONDOWN == uMsg )
  821.     {
  822.         INT x = LOWORD(lParam);
  823.         if( x < (INT)m_d3dsdBackBuffer.Width / 2 )
  824.             m_bLeftActive = TRUE;
  825.         else
  826.             m_bLeftActive = FALSE;
  827.     }
  828.  
  829.     return CD3DApplication::MsgProc( hWnd, uMsg, wParam, lParam );
  830. }
  831.  
  832.  
  833.  
  834.  
  835. //-----------------------------------------------------------------------------
  836. // Name: CullObjects()
  837. // Desc: Cull each object in the CCullableThing array
  838. //-----------------------------------------------------------------------------
  839. VOID CMyD3DApplication::CullObjects(VOID)
  840. {
  841.     CCullableThing* pCullableThing;
  842.  
  843.     for( DWORD iThing = 0; iThing < m_dwNumCullableThings; iThing++ )
  844.     {
  845.         pCullableThing = &m_CullableThingArray[iThing];
  846.         pCullableThing->m_cullstate = CullObject( &m_cullinfo, 
  847.             pCullableThing->m_vecBoundsWorld, pCullableThing->m_planeBoundsWorld );
  848.     }
  849. }
  850.  
  851.  
  852.  
  853.  
  854. //-----------------------------------------------------------------------------
  855. // Name: UpdateCullInfo()
  856. // Desc: Sets up the frustum planes, endpoints, and center for the frustum
  857. //       defined by a given view matrix and projection matrix.  This info will 
  858. //       be used when culling each object in CullObject().
  859. //-----------------------------------------------------------------------------
  860. VOID UpdateCullInfo( CULLINFO* pCullInfo, D3DXMATRIX* pMatView, D3DXMATRIX* pMatProj )
  861. {
  862.     D3DXMATRIX mat;
  863.  
  864.     D3DXMatrixMultiply( &mat, pMatView, pMatProj );
  865.     D3DXMatrixInverse( &mat, NULL, &mat );
  866.  
  867.     pCullInfo->vecFrustum[0] = D3DXVECTOR3(-1.0f, -1.0f,  0.0f); // xyz
  868.     pCullInfo->vecFrustum[1] = D3DXVECTOR3( 1.0f, -1.0f,  0.0f); // Xyz
  869.     pCullInfo->vecFrustum[2] = D3DXVECTOR3(-1.0f,  1.0f,  0.0f); // xYz
  870.     pCullInfo->vecFrustum[3] = D3DXVECTOR3( 1.0f,  1.0f,  0.0f); // XYz
  871.     pCullInfo->vecFrustum[4] = D3DXVECTOR3(-1.0f, -1.0f,  1.0f); // xyZ
  872.     pCullInfo->vecFrustum[5] = D3DXVECTOR3( 1.0f, -1.0f,  1.0f); // XyZ
  873.     pCullInfo->vecFrustum[6] = D3DXVECTOR3(-1.0f,  1.0f,  1.0f); // xYZ
  874.     pCullInfo->vecFrustum[7] = D3DXVECTOR3( 1.0f,  1.0f,  1.0f); // XYZ
  875.  
  876.     for( INT i = 0; i < 8; i++ )
  877.         D3DXVec3TransformCoord( &pCullInfo->vecFrustum[i], &pCullInfo->vecFrustum[i], &mat );
  878.  
  879.     D3DXPlaneFromPoints( &pCullInfo->planeFrustum[0], &pCullInfo->vecFrustum[0], 
  880.         &pCullInfo->vecFrustum[1], &pCullInfo->vecFrustum[2] ); // Near
  881.     D3DXPlaneFromPoints( &pCullInfo->planeFrustum[1], &pCullInfo->vecFrustum[6], 
  882.         &pCullInfo->vecFrustum[7], &pCullInfo->vecFrustum[5] ); // Far
  883.     D3DXPlaneFromPoints( &pCullInfo->planeFrustum[2], &pCullInfo->vecFrustum[2], 
  884.         &pCullInfo->vecFrustum[6], &pCullInfo->vecFrustum[4] ); // Left
  885.     D3DXPlaneFromPoints( &pCullInfo->planeFrustum[3], &pCullInfo->vecFrustum[7], 
  886.         &pCullInfo->vecFrustum[3], &pCullInfo->vecFrustum[5] ); // Right
  887.     D3DXPlaneFromPoints( &pCullInfo->planeFrustum[4], &pCullInfo->vecFrustum[2], 
  888.         &pCullInfo->vecFrustum[3], &pCullInfo->vecFrustum[6] ); // Top
  889.     D3DXPlaneFromPoints( &pCullInfo->planeFrustum[5], &pCullInfo->vecFrustum[1], 
  890.         &pCullInfo->vecFrustum[0], &pCullInfo->vecFrustum[4] ); // Bottom
  891. }
  892.  
  893.  
  894.  
  895.  
  896. //-----------------------------------------------------------------------------
  897. // Name: CullObject()
  898. // Desc: Determine the cullstate for an object bounding box (OBB).  
  899. //       The algorithm is:
  900. //       1) If any OBB corner pt is inside the frustum, return CS_INSIDE
  901. //       2) Else if all OBB corner pts are outside a single frustum plane, 
  902. //          return CS_OUTSIDE
  903. //       3) Else if any frustum edge penetrates a face of the OBB, return 
  904. //          CS_INSIDE_SLOW
  905. //       4) Else if any OBB edge penetrates a face of the frustum, return
  906. //          CS_INSIDE_SLOW
  907. //       5) Else if any point in the frustum is outside any plane of the 
  908. //          OBB, return CS_OUTSIDE_SLOW
  909. //       6) Else return CS_INSIDE_SLOW
  910. //-----------------------------------------------------------------------------
  911. CULLSTATE CullObject( CULLINFO* pCullInfo, D3DXVECTOR3* pVecBounds, 
  912.                       D3DXPLANE* pPlaneBounds )
  913. {
  914.     BYTE bOutside[8];
  915.     ZeroMemory( &bOutside, sizeof(bOutside) );
  916.  
  917.     // Check boundary vertices against all 6 frustum planes, 
  918.     // and store result (1 if outside) in a bitfield
  919.     for( int iPoint = 0; iPoint < 8; iPoint++ )
  920.     {
  921.         for( int iPlane = 0; iPlane < 6; iPlane++ )
  922.         {
  923.             if( pCullInfo->planeFrustum[iPlane].a * pVecBounds[iPoint].x +
  924.                 pCullInfo->planeFrustum[iPlane].b * pVecBounds[iPoint].y +
  925.                 pCullInfo->planeFrustum[iPlane].c * pVecBounds[iPoint].z +
  926.                 pCullInfo->planeFrustum[iPlane].d < 0)
  927.             {
  928.                 bOutside[iPoint] |= (1 << iPlane);
  929.             }
  930.         }
  931.         // If any point is inside all 6 frustum planes, it is inside
  932.         // the frustum, so the object must be rendered.
  933.         if( bOutside[iPoint] == 0 )
  934.             return CS_INSIDE;
  935.     }
  936.  
  937.     // If all points are outside any single frustum plane, the object is
  938.     // outside the frustum
  939.     if( (bOutside[0] & bOutside[1] & bOutside[2] & bOutside[3] & 
  940.         bOutside[4] & bOutside[5] & bOutside[6] & bOutside[7]) != 0 )
  941.     {
  942.         return CS_OUTSIDE;
  943.     }
  944.  
  945.     // Now see if any of the frustum edges penetrate any of the faces of
  946.     // the bounding box
  947.     D3DXVECTOR3 edge[12][2] = 
  948.     {
  949.         pCullInfo->vecFrustum[0], pCullInfo->vecFrustum[1], // front bottom
  950.         pCullInfo->vecFrustum[2], pCullInfo->vecFrustum[3], // front top
  951.         pCullInfo->vecFrustum[0], pCullInfo->vecFrustum[2], // front left
  952.         pCullInfo->vecFrustum[1], pCullInfo->vecFrustum[3], // front right
  953.         pCullInfo->vecFrustum[4], pCullInfo->vecFrustum[5], // back bottom
  954.         pCullInfo->vecFrustum[6], pCullInfo->vecFrustum[7], // back top
  955.         pCullInfo->vecFrustum[4], pCullInfo->vecFrustum[6], // back left
  956.         pCullInfo->vecFrustum[5], pCullInfo->vecFrustum[7], // back right
  957.         pCullInfo->vecFrustum[0], pCullInfo->vecFrustum[4], // left bottom
  958.         pCullInfo->vecFrustum[2], pCullInfo->vecFrustum[6], // left top
  959.         pCullInfo->vecFrustum[1], pCullInfo->vecFrustum[5], // right bottom
  960.         pCullInfo->vecFrustum[3], pCullInfo->vecFrustum[7], // right top
  961.     };
  962.     D3DXVECTOR3 face[6][4] =
  963.     {
  964.         pVecBounds[0], pVecBounds[2], pVecBounds[3], pVecBounds[1], // front
  965.         pVecBounds[4], pVecBounds[5], pVecBounds[7], pVecBounds[6], // back
  966.         pVecBounds[0], pVecBounds[4], pVecBounds[6], pVecBounds[2], // left
  967.         pVecBounds[1], pVecBounds[3], pVecBounds[7], pVecBounds[5], // right
  968.         pVecBounds[2], pVecBounds[6], pVecBounds[7], pVecBounds[3], // top
  969.         pVecBounds[0], pVecBounds[4], pVecBounds[5], pVecBounds[1], // bottom
  970.     };
  971.     D3DXVECTOR3* pEdge;
  972.     D3DXVECTOR3* pFace;
  973.     pEdge = &edge[0][0];
  974.     for( INT iEdge = 0; iEdge < 12; iEdge++ )
  975.     {
  976.         pFace = &face[0][0];
  977.         for( INT iFace = 0; iFace < 6; iFace++ )
  978.         {
  979.             if( EdgeIntersectsFace( pEdge, pFace, &pPlaneBounds[iFace] ) )
  980.             {
  981.                 return CS_INSIDE_SLOW;
  982.             }
  983.             pFace += 4;
  984.         }
  985.         pEdge += 2;
  986.     }
  987.  
  988.     // Now see if any of the bounding box edges penetrate any of the faces of
  989.     // the frustum
  990.     D3DXVECTOR3 edge2[12][2] = 
  991.     {
  992.         pVecBounds[0], pVecBounds[1], // front bottom
  993.         pVecBounds[2], pVecBounds[3], // front top
  994.         pVecBounds[0], pVecBounds[2], // front left
  995.         pVecBounds[1], pVecBounds[3], // front right
  996.         pVecBounds[4], pVecBounds[5], // back bottom
  997.         pVecBounds[6], pVecBounds[7], // back top
  998.         pVecBounds[4], pVecBounds[6], // back left
  999.         pVecBounds[5], pVecBounds[7], // back right
  1000.         pVecBounds[0], pVecBounds[4], // left bottom
  1001.         pVecBounds[2], pVecBounds[6], // left top
  1002.         pVecBounds[1], pVecBounds[5], // right bottom
  1003.         pVecBounds[3], pVecBounds[7], // right top
  1004.     };
  1005.     D3DXVECTOR3 face2[6][4] =
  1006.     {
  1007.         pCullInfo->vecFrustum[0], pCullInfo->vecFrustum[2], pCullInfo->vecFrustum[3], pCullInfo->vecFrustum[1], // front
  1008.         pCullInfo->vecFrustum[4], pCullInfo->vecFrustum[5], pCullInfo->vecFrustum[7], pCullInfo->vecFrustum[6], // back
  1009.         pCullInfo->vecFrustum[0], pCullInfo->vecFrustum[4], pCullInfo->vecFrustum[6], pCullInfo->vecFrustum[2], // left
  1010.         pCullInfo->vecFrustum[1], pCullInfo->vecFrustum[3], pCullInfo->vecFrustum[7], pCullInfo->vecFrustum[5], // right
  1011.         pCullInfo->vecFrustum[2], pCullInfo->vecFrustum[6], pCullInfo->vecFrustum[7], pCullInfo->vecFrustum[3], // top
  1012.         pCullInfo->vecFrustum[0], pCullInfo->vecFrustum[4], pCullInfo->vecFrustum[5], pCullInfo->vecFrustum[1], // bottom
  1013.     };
  1014.     pEdge = &edge2[0][0];
  1015.     for( iEdge = 0; iEdge < 12; iEdge++ )
  1016.     {
  1017.         pFace = &face2[0][0];
  1018.         for( INT iFace = 0; iFace < 6; iFace++ )
  1019.         {
  1020.             if( EdgeIntersectsFace( pEdge, pFace, &pCullInfo->planeFrustum[iFace] ) )
  1021.             {
  1022.                 return CS_INSIDE_SLOW;
  1023.             }
  1024.             pFace += 4;
  1025.         }
  1026.         pEdge += 2;
  1027.     }
  1028.  
  1029.     // Now see if frustum is contained in bounding box
  1030.     // If any frustum corner point is outside any plane of the bounding box,
  1031.     // the frustum is not contained in the bounding box, so the object
  1032.     // is outside the frustum
  1033.     for( INT iPlane = 0; iPlane < 6; iPlane++ )
  1034.     {
  1035.         if( pPlaneBounds[iPlane].a * pCullInfo->vecFrustum[0].x +
  1036.             pPlaneBounds[iPlane].b * pCullInfo->vecFrustum[0].y +
  1037.             pPlaneBounds[iPlane].c * pCullInfo->vecFrustum[0].z +
  1038.             pPlaneBounds[iPlane].d  < 0 )
  1039.         {
  1040.             return CS_OUTSIDE_SLOW;
  1041.         }
  1042.     }
  1043.  
  1044.     // Bounding box must contain the frustum, so render the object
  1045.     return CS_INSIDE_SLOW;
  1046. }
  1047.  
  1048.  
  1049.  
  1050.  
  1051. //-----------------------------------------------------------------------------
  1052. // Name: EdgeIntersectsFace()
  1053. // Desc: Determine if the edge bounded by the two vectors in pEdges intersects
  1054. //       the quadrilateral described by the four vectors in pFacePoints.  
  1055. //       Note: pPlane could be derived from pFacePoints using 
  1056. //       D3DXPlaneFromPoints, but it is precomputed in advance for greater
  1057. //       speed.
  1058. //-----------------------------------------------------------------------------
  1059. BOOL EdgeIntersectsFace( D3DXVECTOR3* pEdges, D3DXVECTOR3* pFacePoints, 
  1060.                          D3DXPLANE* pPlane )
  1061. {
  1062.     // If both edge points are on the same side of the plane, the edge does
  1063.     // not intersect the face
  1064.     FLOAT fDist1;
  1065.     FLOAT fDist2;
  1066.     fDist1 = pPlane->a * pEdges[0].x + pPlane->b * pEdges[0].y +
  1067.              pPlane->c * pEdges[0].z + pPlane->d;
  1068.     fDist2 = pPlane->a * pEdges[1].x + pPlane->b * pEdges[1].y +
  1069.              pPlane->c * pEdges[1].z + pPlane->d;
  1070.     if( fDist1 > 0 && fDist2 > 0 ||
  1071.         fDist1 < 0 && fDist2 < 0 )
  1072.     {
  1073.         return FALSE;
  1074.     }
  1075.  
  1076.     // Find point of intersection between edge and face plane (if they're
  1077.     // parallel, edge does not intersect face and D3DXPlaneIntersectLine 
  1078.     // returns NULL)
  1079.     D3DXVECTOR3 ptIntersection;
  1080.     if( NULL == D3DXPlaneIntersectLine( &ptIntersection, pPlane, &pEdges[0], &pEdges[1] ) )
  1081.         return FALSE;
  1082.  
  1083.     // Project onto a 2D plane to make the pt-in-poly test easier
  1084.     FLOAT fAbsA = (pPlane->a > 0 ? pPlane->a : -pPlane->a);
  1085.     FLOAT fAbsB = (pPlane->b > 0 ? pPlane->b : -pPlane->b);
  1086.     FLOAT fAbsC = (pPlane->c > 0 ? pPlane->c : -pPlane->c);
  1087.     D3DXVECTOR2 facePoints[4];
  1088.     D3DXVECTOR2 point;
  1089.     if( fAbsA > fAbsB && fAbsA > fAbsC )
  1090.     {
  1091.         // Plane is mainly pointing along X axis, so use Y and Z
  1092.         for( INT i = 0; i < 4; i++)
  1093.         {
  1094.             facePoints[i].x = pFacePoints[i].y;
  1095.             facePoints[i].y = pFacePoints[i].z;
  1096.         }
  1097.         point.x = ptIntersection.y;
  1098.         point.y = ptIntersection.z;
  1099.     }
  1100.     else if( fAbsB > fAbsA && fAbsB > fAbsC )
  1101.     {
  1102.         // Plane is mainly pointing along Y axis, so use X and Z
  1103.         for( INT i = 0; i < 4; i++)
  1104.         {
  1105.             facePoints[i].x = pFacePoints[i].x;
  1106.             facePoints[i].y = pFacePoints[i].z;
  1107.         }
  1108.         point.x = ptIntersection.x;
  1109.         point.y = ptIntersection.z;
  1110.     }
  1111.     else
  1112.     {
  1113.         // Plane is mainly pointing along Z axis, so use X and Y
  1114.         for( INT i = 0; i < 4; i++)
  1115.         {
  1116.             facePoints[i].x = pFacePoints[i].x;
  1117.             facePoints[i].y = pFacePoints[i].y;
  1118.         }
  1119.         point.x = ptIntersection.x;
  1120.         point.y = ptIntersection.y;
  1121.     }
  1122.  
  1123.     // If point is on the outside of any of the face edges, it is
  1124.     // outside the face.  
  1125.     // We can do this by taking the determinant of the following matrix:
  1126.     // | x0 y0 1 |
  1127.     // | x1 y1 1 |
  1128.     // | x2 y2 1 |
  1129.     // where (x0,y0) and (x1,y1) are points on the face edge and (x2,y2) 
  1130.     // is our test point.  If this value is positive, the test point is
  1131.     // "to the left" of the line.  To determine whether a point needs to
  1132.     // be "to the right" or "to the left" of the four lines to qualify as
  1133.     // inside the face, we need to see if the faces are specified in 
  1134.     // clockwise or counter-clockwise order (it could be either, since the
  1135.     // edge could be penetrating from either side).  To determine this, we
  1136.     // do the same test to see if the third point is "to the right" or 
  1137.     // "to the left" of the line formed by the first two points.
  1138.     // See http://forum.swarthmore.edu/dr.math/problems/scott5.31.96.html
  1139.     FLOAT x0, x1, x2, y0, y1, y2;
  1140.     x0 = facePoints[0].x;
  1141.     y0 = facePoints[0].y;
  1142.     x1 = facePoints[1].x;
  1143.     y1 = facePoints[1].y;
  1144.     x2 = facePoints[2].x;
  1145.     y2 = facePoints[2].y;
  1146.     BOOL bClockwise = FALSE;
  1147.     if( x1*y2 - y1*x2 - x0*y2 + y0*x2 + x0*y1 - y0*x1 < 0 )
  1148.         bClockwise = TRUE;
  1149.     x2 = point.x;
  1150.     y2 = point.y;
  1151.     for( INT i = 0; i < 4; i++ )
  1152.     {
  1153.         x0 = facePoints[i].x;
  1154.         y0 = facePoints[i].y;
  1155.         if( i < 3 )
  1156.         {
  1157.             x1 = facePoints[i+1].x;
  1158.             y1 = facePoints[i+1].y;
  1159.         }
  1160.         else
  1161.         {
  1162.             x1 = facePoints[0].x;
  1163.             y1 = facePoints[0].y;
  1164.         }
  1165.         if( ( x1*y2 - y1*x2 - x0*y2 + y0*x2 + x0*y1 - y0*x1 > 0 ) == bClockwise )
  1166.             return FALSE;
  1167.     }
  1168.  
  1169.     // If we get here, the point is inside all four face edges, 
  1170.     // so it's inside the face.
  1171.     return TRUE;
  1172. }
  1173.